#include<arbb.hpp>
using namespace arbb;	
// Used by the mark array
#define UNVISITED 0
#define VISITED 1

//#include "link.h"
#include "llist.h"

#include "graph.h"


class Edge {
public:
  i32 vertex, weight;
  Edge() { vertex = -1; weight = -1; }
  Edge(i32 v, i32 w) { vertex = v; weight = w; }
};

// Overload for the Edge << operator
ostream& operator << (ostream& s, Edge e)
  { return(s << "(" << e.vertex << ", " << e.weight << ")"); }

class Graphl : public Graph { // Implement adjacency list
private:
  i32 numVertex, numEdge;     // Number of vertices, edges
  List<Edge>** vertex; // List headers
  i32 *mark;                  // Pointer to mark array
public:
  Graphl(i32 numVert) { // Make graph with numVert vertices
    i32 i;
    numVertex = numVert;  numEdge = 0;
    mark = new int[numVert]; // Initialize mark array
    _for(i=0, i<numVertex, i++)
      {
	mark[i] = UNVISITED;
      }_end_for;
    // Create and initialize adjacency lists
    vertex = (List<Edge>**) new List<Edge>*[numVertex];
    _for(i=0, i<numVertex, i++)
      {
	vertex[i] = new LList<Edge>(0);
      }_end_for;
  }

  ~Graphl() {       // Destructor
    delete [] mark; // Return dynamically allocated memory
    _for(i32 i=0, i<numVertex; i++)
      {
	delete  vertex[i];//[]
      }_end_for;
    delete [] vertex;
  }

  i32 n() { return numVertex; } // Number of vertices
  i32 e() { return numEdge; }   // Number of edges

  i32 first(i32 v) { // Return first neighbor of v
    Edge it;
    vertex[v]->setStart();
    _if(vertex[v]->getValue(it))
      {
	return it.vertex;
      }_else
	 {
	   return numVertex;  // Return n if none
	 }_end_if;
  }

  i32 next(i32 v1, i32 v2) { // Gete v1's neighbor after v2
    Edge it;
    vertex[v1]->getValue(it);
    _if(it.vertex == v2)
      {
	vertex[v1]->next();
      }_else
	 { // Start from beginning of list
	   vertex[v1]->setStart();
	   while (vertex[v1]->getValue(it) && (it.vertex <= v2))
	     vertex[v1]->next();
	 }_end_if;
    _if(vertex[v1]->getValue(it))
      {
	return it.vertex;
      }_else
	 {
	   return numVertex;  // Return n if none
	 }_end_if;
  }

  // Set edge (v1, v2) to wgt
  void setEdge(i32 v1, i32 v2, i32 wgt) {
    //Assert(wgt>0, "Illegal weight value");
    Edge it(v2, wgt);
    Edge curr;
    vertex[v1]->getValue(curr);
    _if(curr.vertex != v2) // If not already there, search
      {
	_for(vertex[v1]->setStart(),vertex[v1]->getValue(curr), vertex[v1]->next())
	  {
	    _if(curr.vertex >= v2)
	      {
		break;
	      }_end_if;
	  }_end_for;
      }_end_if;
    _if(curr.vertex == v2)  // Clear out the current one
      {
	vertex[v1]->remove(curr);
      }_else
	 {
	   numEdge++;
	 }end_if;
    vertex[v1]->insert(it);
  }

  void delEdge(i32 v1, i32 v2) { // Delete edge (v1, v2)
    Edge curr;
    vertex[v1]->getValue(curr);
    _if(curr.vertex != v2)
      {  // If not already there, search
	_for(vertex[v1]->setStart(),vertex[v1]->getValue(curr), vertex[v1]->next())
	  {
	    _if(curr.vertex >= v2)
	      {
		break;
	      }_end_if;
	  }_end_for;
      }_end_if;
    _if(curr.vertex == v2)
      {  // If not, then there is none
	vertex[v1]->remove(curr);
	numEdge--;
      }_end_if;
  }
  
  i32 weight(i32 v1, i32 v2) { // Return weight of (v1, v2)
    Edge curr;
    vertex[v1]->getValue(curr);
    _if(curr.vertex != v2) // If not already there, search
      {
	_for(vertex[v1]->setStart(),vertex[v1]->getValue(curr), vertex[v1]->next())
	  {
	    _if(curr.vertex >= v2)
	      {
		break;
	      }_end_if;
	  }_end_for;
      }_end_if;
    _if(curr.vertex == v2)
      {
	return curr.weight;
      }_else
	 {
	   return 0;  // No such edge
	 }_end_if;
  }

  i32 getMark(i32 v) { return mark[v]; }
  void setMark(i32 v, i32 val) { mark[v] = val; }
};

//#include "graphutil.cpp"
